// system.cc 
//	Nachos initialization and cleanup routines.
//
// Copyright (c) 1992-1993 The Regents of the University of California.
// All rights reserved.  See copyright.h for copyright notice and limitation 
// of liability and disclaimer of warranty provisions.

#include "copyright.h"
#include "system.h"

// This defines *all* of the global data structures used by Nachos.
// These are all initialized and de-allocated by this file.

Thread *currentThread;			// the thread we are running now
Thread *threadToBeDestroyed;  		// the thread that just finished
Scheduler *scheduler;			// the ready list
Interrupt *interrupt;			// interrupt status
Statistics *stats;			// performance metrics
Timer *timer;				// the hardware timer device,
					// for invoking context switches

#ifdef FILESYS_NEEDED
FileSystem  *fileSystem;
#endif

#ifdef FILESYS
SynchDisk   *synchDisk;
#endif

#ifdef USER_PROGRAM	// requires either FILESYS or FILESYS_STUB
Machine *machine;	// user program memory and registers
BitMap *memorybitmap;
HashSet *InvertedPageTable;
#endif

#ifdef NETWORK
PostOffice *postOffice;
#endif

int Threadidused[MAX_THREAD_NUM];
int Threadnum;

int printts;

List *ThreadList;
void* LockList[MAX_LOCK_NUM];

char edge[MAX_THREAD_NUM][MAX_LOCK_NUM];

// External definition, to allow us to take a pointer to this function
extern void Cleanup();


//----------------------------------------------------------------------
// TimerInterruptHandler
// 	Interrupt handler for the timer device.  The timer device is
//	set up to interrupt the CPU periodically (once every TimerTicks).
//	This routine is called each time there is a timer interrupt,
//	with interrupts disabled.
//
//	Note that instead of calling Yield() directly (which would
//	suspend the interrupt handler, not the interrupted thread
//	which is what we wanted to context switch), we set a flag
//	so that once the interrupt handler is done, it will appear as 
//	if the interrupted thread called Yield at the point it is 
//	was interrupted.
//void* *LockList
//	"dummy" is because every interrupt handler takes one argument,
//		whether it needs it or not.
//----------------------------------------------------------------------
static void
TimerInterruptHandler(int dummy)
{
    if (interrupt->getStatus() != IdleMode)
	interrupt->YieldOnReturn();
}

//----------------------------------------------------------------------
// Initialize
// 	Initialize Nachos global data structures.  Interpret command
//	line arguments in order to determine flags for the initialization.  
// 
//	"argc" is the number of command line arguments (including the name
//		of the command) -- ex: "nachos -d +" -> argc = 3 
//	"argv" is an array of strings, one for each command line argument
//		ex: "nachos -d +" -> argv = {"nachos", "-d", "+"}
//----------------------------------------------------------------------
void
Initialize(int argc, char **argv)
{
    int argCount;
    char* debugArgs = "";
    bool randomYield = FALSE;

#ifdef USER_PROGRAM
    bool debugUserProg = FALSE;	// single step user program
#endif
#ifdef FILESYS_NEEDED
    bool format = FALSE;	// format disk
#endif
#ifdef NETWORK
    double rely = 1;		// network reliability
    int netname = 0;		// UNIX socket name
#endif
    
    printts = 0;

    for (argc--, argv++; argc > 0; argc -= argCount, argv += argCount) {
	argCount = 1;
	if (!strcmp(*argv, "-d")) {
	    if (argc == 1)
		debugArgs = "+";	// turn on all debug flags
	    else {
	    	debugArgs = *(argv + 1);
	    	argCount = 2;
	    }
	} else if (!strcmp(*argv, "-rs")) {
	    ASSERT(argc > 1);
	    RandomInit(atoi(*(argv + 1)));	// initialize pseudo-random
						// number generator
	    randomYield = TRUE;
	    argCount = 2;
	} else if (!strcmp(*argv, "-ts")) {
            printts = 1;
        }
#ifdef USER_PROGRAM
        memorybitmap = new BitMap(4096);
        InvertedPageTable = new HashSet(29);
	if (!strcmp(*argv, "-s"))
	    debugUserProg = TRUE;
#endif
#ifdef FILESYS_NEEDED
	if (!strcmp(*argv, "-f"))
	    format = TRUE;
#endif
#ifdef NETWORK
	if (!strcmp(*argv, "-l")) {
	    ASSERT(argc > 1);
	    rely = atof(*(argv + 1));
	    argCount = 2;
	} else if (!strcmp(*argv, "-m")) {
	    ASSERT(argc > 1);
	    netname = atoi(*(argv + 1));
	    argCount = 2;
	}
#endif
    }


    for (int i = 0; i < MAX_THREAD_NUM; i++) {
        Threadidused[i] = -1;
    }
    Threadnum = 0;

    ThreadList = new List;

    for (int i = 0; i < MAX_LOCK_NUM; i++) {
	LockList[i] = NULL;
    }

    for (int i = 0; i < MAX_THREAD_NUM; i++) 
        for (int j = 0; j < MAX_LOCK_NUM; j++)
            edge[i][j] = 0;

    DebugInit(debugArgs);			// initialize DEBUG messages
    stats = new Statistics();			// collect statistics
    interrupt = new Interrupt;			// start up interrupt handling
    scheduler = new Scheduler();		// initialize the ready queue
    if (randomYield)				// start the timer (if needed)
	timer = new Timer(TimerInterruptHandler, 0, randomYield);

    threadToBeDestroyed = NULL;

    // We didn't explicitly allocate the current thread we are running in.
    // But if it ever tries to give up the CPU, we better have a Thread
    // object to save its state. 
    currentThread = new Thread("main");		
    currentThread->setStatus(RUNNING);

    interrupt->Enable();
    CallOnUserAbort(Cleanup);			// if user hits ctl-C
    
#ifdef USER_PROGRAM
    machine = new Machine(debugUserProg);	// this must come first
#endif

#ifdef FILESYS
    synchDisk = new SynchDisk("DISK");
#endif

#ifdef FILESYS_NEEDED
    fileSystem = new FileSystem(format);
#endif

#ifdef NETWORK
    postOffice = new PostOffice(netname, rely, 10);
#endif
}

//----------------------------------------------------------------------
// Cleanup
// 	Nachos is halting.  De-allocate global data structures.
//----------------------------------------------------------------------
void
Cleanup()
{
    printf("\nCleaning up...\n");
#ifdef NETWORK
    delete postOffice;
#endif
    
#ifdef USER_PROGRAM
    delete machine;
#endif

#ifdef FILESYS_NEEDED
    delete fileSystem;
#endif

#ifdef FILESYS
    delete synchDisk;
#endif
    
    delete timer;
    delete scheduler;
    delete interrupt;
    
    Exit(0);
}

void
PrintThreadStatus()
{
    if (printts == 0) return;

    Thread *FirstItem = (Thread*)ThreadList->Remove();
    printf("\n\n=========== Thread Status ===========\n");
    printf("tid\tName            Status\n");
    printf("%d\t%-16s%s\n", FirstItem->getThreadid(), FirstItem->getName(), FirstItem->getStatus());

    ThreadList->Append((void*)FirstItem);
    Thread *Item;

    while((Item = (Thread*)ThreadList->Remove()) != FirstItem) {
        printf("%d\t%-16s%s\n", Item->getThreadid(), Item->getName(), Item->getStatus());
        ThreadList->Append((void*)Item);
    }
    ThreadList->Prepend((void*)Item);
    printf("=====================================\n\n");
}

int
dfsThread(int tid, int *lockinedge, int *threadinedge)
{
    int i;
    for (i = 0; i < MAX_LOCK_NUM; i++) {
        if (edge[tid][i] == 2) {
            if (lockinedge[i] != 0) {
                printf("lock%d<-", i);
                return i;
            }
            else {
                lockinedge[i] = 1;
                int ret = dfsLock(i, lockinedge, threadinedge);
                if (ret != -1) {
                    printf("lock%d<-", i);
                    return ret;
                }
                lockinedge[i] = 0;
            }
        }
    }
    return -1;
}

int
dfsLock(int lockid, int *lockinedge, int *threadinedge)
{
    int i;
    for (i = 0; i < MAX_THREAD_NUM; i++) {
        if (edge[i][lockid] == 1) {
            if (threadinedge[i] != 0) {
                printf("thread%d<-", i);
                return i;
            }
            else {
                threadinedge[i] = 1;
                int ret = dfsThread(i, lockinedge, threadinedge);
                if (ret != -1) {
                    printf("thread%d<-", i);
                    return ret;
                }
                threadinedge[i] = 0;
            }
        }
    }
    return -1;    
}

int
CheckDeadLock()
{
    int i, j;
    int lockinedge[MAX_LOCK_NUM] = {0};
    int threadinedge[MAX_THREAD_NUM] = {0};
    printf("Check Dead Lock\n");
    for (i = 0; i < MAX_THREAD_NUM; i++)
        for (j = 0; j < MAX_LOCK_NUM; j++) {
            if (edge[i][j] == 1) {
                lockinedge[j] = 1;
                threadinedge[i] = 1;
                int ret = dfsThread(i, lockinedge, threadinedge);
                if (ret != -1) {
                    printf("thread%d<-lock%d\n", i, j);
                    return ret;
                }
                lockinedge[j] = 0;
                threadinedge[i] = 0;
            }
        }
    return -1;
}
